﻿//力扣：20. 有效的括号
//https://leetcode.cn/problems/valid-parentheses/description/


//基本逻辑思路：通过使用栈保存左括号，逐个匹配右括号，确保所有括号按正确顺序闭合，保证了字符串的括号有效性。
//1. 长度检查：首先判断字符串长度是否为奇数，若为奇数则直接返回 false。
//因为有效的括号字符串必须是偶数长度，左括号和右括号数量相等。
//
//2. 栈操作：
//遍历字符串 s 中的每个字符：
//    左括号（(, { ,[）：将左括号字符压入栈中，以便稍后与右括号进行匹配。
//    右括号（), }, ]）：从栈中弹出一个左括号，判断是否与当前的右括号匹配。
//        如果栈为空（意味着没有对应的左括号），或者弹出的左括号与当前右括号不匹配，则返回 false。
//        否则继续循环处理下一个字符。
//3. 最终判断：循环结束后检查栈是否为空。若栈为空，说明所有的左括号和右括号都成功匹配，返回 true；否则返回 false，表示括号未全部匹配。

class Solution
{
public:
    bool isValid(string s)
    {
        if (s.size() % 2 == 1)
        {
            return false;                                           // 如果字符数量是奇数，不可能是有效的括号序列
        }

        stack<char> st;                                             // 定义一个栈，用于存储左括号

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                st.push(s[i]);                                      // 遇到左括号，压入栈中
            }
            else
            {
                if (st.empty())
                {
                    return false;                                   // 栈为空时遇到右括号，说明不匹配
                }

                char tmp = st.top();
                st.pop();

                // 判断栈顶左括号与当前右括号是否匹配
                if ((tmp == '(' && s[i] != ')') ||
                    (tmp == '{' && s[i] != '}') ||
                    (tmp == '[' && s[i] != ']'))
                {
                    return false;                                   // 若不匹配，直接返回false
                }
            }
        }

        return st.empty();                                          // 检查栈是否为空，若为空则全部匹配成功
    }
};